Functional verification is widely acknowledged to be a bottleneck in the hardware design cycle. Indeed, up to 70% of design development time and resources are typically spent on functional verification. Allowing users to find design flaws, and fixing them in a subsequent release would be unwise and costly for three main reasons: (1) harm to reputation and brand-name; (2) a high cost of recall and replacement when there is a large installed base; and (3) litigation in the event that design flaws caused injury.
In current industrial practice, dynamic verification is the main functional verification technique for large and complex designs. Dynamic verification is accomplished by generating a large number of tests using random test generators, simulating the tests on the design-under-test, and checking that the design-under-test behaves according to its specification.
The rationale behind verification by simulation is that one acquires confidence in the correctness of a design-under-test by running a set of test cases that encompass a sufficiently large number of different cases, which in some sense is assumed to be a representative sample of the full space of possible cases. The ability of the design-under-test to correctly handle all cases is inferred from the correct handling of the cases actually tested. This approach is discussed, for example, in the document User Defined Coverage—A Tool Supported Methodology for Design Verification, Raanan Grinwald, Eran Harel, Michael Orgad, Shmuel Ur, and Avi Ziv, Proc. 38th Design Automation Conference (DAC38), pages 158-163, 1998. When conducting simulations, it is desirable to define a particular subspace, which is considered to be “interesting” in terms of verification, and then to generate tests selected at random that cover the subspace.
Test cases developed by algorithms such as the foregoing are typically implemented on a test generator, which may optionally bias the tests based on internal testing knowledge. Such test generators are described in the following documents: Model-Based Test Generation For Processor Design Verification, Y. Lichtenstein, Y. Malka and A. Aharon, Innovative Applications of Artificial Intelligence (IAAI), AAAI Press, 1994; Constraint Satisfaction for Test Program Generation, L. Fournier, D. Lewin, M. Levinger, E. Roytman and Gil Shurek, Int. Phoenix Conference on Computers and Communications, March 1995; and Test Program Generation for Functional Verification of PowerPC Processors in IBM, A. Aharon, D. Goodman, M. Levinger, Y. Lichtenstein, Y. Malka, C. Metzger, M. Molcho and G. Shurek, 32nd Design Automation Conference, San Francisco, June 1995, pp. 279-285.
The term coverage concerns checking and showing that testing has been thorough. Coverage is any metric of completeness with respect to a test selection criterion for the design-under-test. Simply stated, the idea is to create in some systematic fashion a large and comprehensive list of tasks, and check that in the testing phase each task was executed. A common coverage metric used in the industry is statement coverage, which is a metric of the number of source language statements executed under test. Coverage measurement tools for user-defined coverage models are disclosed in U.S. Pat. No. 6,356,858 to Malka et al., of common assignee herewith, and herein incorporated by reference.
One of the uses of coverage is to find good regression-suites. A regression test suite, referred to herein as a regression suite, is a group of tests, which are repeated on the design-under-test after a modification of the design-under-test, and is intended to show that the behavior of the design-under-test is unchanged except insofar as required by the current modification. To be effective, a regression suite must be sufficiently comprehensive so that it is likely to discover newly introduced design flaws, yet be compact, so that it can be economically repeated many times during the course of the development cycle.
Tests are included in regression suites for different reasons. For example, tests that previously led to the discovery of hard-to-find bugs are often included in regression suites. A complementary approach is to design regression suites so that they yield high coverage, i.e., regression suites that produce coverage at least as high as was thus far attained by the entire verification effort.
One approach for creating high-coverage regression suites is to find the smallest subset of the set of previously executed verification tests that yields comparable coverage. This is an instance of the set cover problem, which is known to be NP-Complete. However, an efficient and simple greedy algorithm can provide a good approximation of the optimal solution. An on-the-fly version of the algorithm produces good results for very large sets of tests, as described in the document, Compacting Regression-Suites On-the-Fly. E. Buchnik and S. Ur, in Proceedings of the 4th Asia Pacific Software Engineering Conference, December 1997, which is herein incorporated by reference. Methods for producing compact regression suites are disclosed in the document, On Minimizing Regression-Suites Using On-Line Set-Cover, E. Buchnik and S. Ur, in Proceedings of Eurostar97: The Fifth European Conference on Software Testing, November 1997, which is herein incorporated by reference.
Regression suites that are built from a predetermined set of tests have several inherent problems. First, they are sensitive to changes in the design-under-test and its environment. Changes in the design may affect the behavior of the tests and affect areas of the test space that are not covered by the regression suite. In addition, tests that were previously used are less likely to find bugs than newer tests that have not-yet been included in the regression suite. Finally, the maintenance cost of such regression suites is high because every test has to be automated and maintained.